/*
    并查集-上

    前置知识 : 无

    并查集的使用是如下的场景
    1）一开始每个元素都拥有自己的集合，在自己的集合里只有这个元素自己
    2）find(i)：查找i所在集合的代表元素，代表元素来代表i所在的集合
    3）boolean isSameSet(a, b)：判断a和b在不在一个集合里
    4）void union(a, b)：a所在集合所有元素 与 b所在集合所有元素 合并成一个集合
    5）各种操作单次调用的均摊时间复杂度为O(1)

    并查集原理图解

    注意：带权并查集的内容是大厂笔试面试冷门内容，会在【挺难】课程里讲述。
    可持久化并查集、可撤销并查集，更是比较冷门的内容，备战比赛的同学自行学习，本课程不再安排讲述

    ================================================

    并查集的两个优化，都发生在find方法里
    1）扁平化（一定要做）
    2）小挂大（可以不做，原论文中是秩的概念，可以理解为 粗略高度 或者 大小）

    并查集的小扩展（下节课的题目重点展示）
    可以定制信息：并查集目前有多少个集合，以及给每个集合打上标签信息

    并查集时间复杂度的理解
    作为如此简单、小巧的结构，
    感性理解单次调用的均摊时间复杂度为O(1)即可，其实为α(n)，阿克曼函数。
    当n=10^80次方即可探明宇宙原子量，α(n)的返回值也不超过6，那就可以认为是O(1)
    并查集的发明者Bernard A. Galler和Michael J. Fischer，
    从1964年证明到1989年才证明完毕，建议记住即可，理解证明难度很大！

    ================================================

    题目1
    并查集模版(牛客)
    路径压缩 + 小挂大
    测试链接 : 
    https://www.nowcoder.com/practice/e7ed657974934a30b2010046536a5372

    ================================================

    题目2
    并查集模版(洛谷)
    用递归函数实现路径压缩
    一般情况下小挂大的优化可以省略的写法
    测试链接 : https://www.luogu.com.cn/problem/P3367

    ================================================

    题目3
    情侣牵手
    n对情侣坐在连续排列的 2n 个座位上，想要牵到对方的手
    人和座位由一个整数数组 row，表示其中 row[i] 是坐在第 i 个座位上的人的ID
    情侣们按顺序编号，第0对是 (0, 1)，第1对是 (2, 3)，以此类推
    返回 最少交换座位的次数，以便每对情侣可以并肩坐在一起
    每次交换可选择任意两人，让他们站起来交换座位
    测试链接 : https://leetcode.cn/problems/couples-holding-hands/

    ================================================

    题目4
    相似字符串组
    如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等
    那么称 X 和 Y 两个字符串相似
    如果这两个字符串本身是相等的，那它们也是相似的
    例如，"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)；
    "rats" 和 "arts" 也是相似的，但是 "star" 不与 "tars"，"rats"，或 "arts" 相似
    总之，它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}
    注意，"tars" 和 "arts" 是在同一组中，即使它们并不相似
    形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。
    给你一个字符串列表 strs列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。
    返回 strs 中有多少字符串组
    测试链接 : https://leetcode.cn/problems/similar-string-groups/

    ================================================

    题目5
    岛屿数量
    给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量
    岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成
    此外，你可以假设该网格的四条边均被水包围
    测试链接 : https://leetcode.cn/problems/number-of-islands/

    注意：本题还可以用洪水填充算法求解，后续【必备】课程会讲述洪水填充算法

    ================================================

    加餐练习：
    130. 被围绕的区域：https://leetcode.cn/problems/surrounded-regions/
    547. 省份数量：https://leetcode.cn/problems/number-of-provinces/
    684. 冗余连接：https://leetcode.cn/problems/redundant-connection/
    695. 岛屿的最大面积：https://leetcode.cn/problems/max-area-of-island/
    261. 以图判树：https://leetcode.cn/problems/graph-valid-tree/
    785. 判断二分图：https://leetcode.cn/problems/is-graph-bipartite/
    886. 可能的二分法：https://leetcode.cn/problems/possible-bipartition/
    990. 等式方程的可满足性：https://leetcode.cn/problems/satisfiability-of-equality-equations/

*/